package completedRDT;

import java.io.File;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import util.HadoopUtil;
import util.ModelOperator;
import util.MyMath;

/**
 * RDTModel, containing operators of managing trees
 * 
 * @author tigerzhong
 * 
 */

public class RDTModel implements java.io.Serializable, java.lang.Cloneable {
    
    /**
     * serialVersionUID
     */
    private static final long serialVersionUID = 1L;
    /**
     * Minimal number at one leaf
     */
    private int minNum = 1;
    /**
     * Number of random trees
     */
    private int numTrees = 30;
    /**
     * Depth of the trees
     */
    private int depth = 12;
    /**
     * Random trees
     */
    private Tree forest[];
    /**
     * Number of the features
     */
    private int numFeatures = 10;
    /**
     * The up bound of features
     */
    private double ubFeature[];
    /**
     * The low boud of features
     */
    private double lbFeature[];
    /**
     * The number of classes in the data set
     */
    private int numClass = 1;
    /**
     * The ratio of major class
     */
    private double ratio = 1.0;

    /* Set and Get*/
    public double getRatio() {
        return ratio;
    }

    public void setRatio(double ratio) {
        this.ratio = ratio;
    }
    
    public int getNumTrees() {
        return numTrees;
    }

    public void setNumTrees(int numTrees) {
        this.numTrees = numTrees;
    }

    public int getDepth() {
        return depth;
    }

    public void setDepth(int depth) {
        this.depth = depth;
    }

    public int getNumFeatures() {
        return numFeatures;
    }

    public void setNumFeatures(int numFeatures) {
        this.numFeatures = numFeatures;
    }

    public int getNumClass() {
        return numClass;
    }

    public void setNumClass(int numClass) {
        this.numClass = numClass;
    }
    public int getMinNum() {
        return minNum;
    }

    public void setMinNum(int minNum) {
        this.minNum = minNum;
    }
    
    public double[] getUbFeature() {
	return ubFeature;
    }

    public void setUbFeature(String ub) {
	String ubFeature[] = ub.split(",",-1);
	this.ubFeature = new double[ubFeature.length];
	for (int i = 0; i < ubFeature.length; i++)
	    this.ubFeature[i] = Double.parseDouble(ubFeature[i]);
    }

    public double[] getLbFeature() {
	return lbFeature;
    }

    public void setLbFeature(String lb) {
	String lbFeature[] = lb.split(",",-1);
	this.lbFeature = new double[lbFeature.length];
	for (int i = 0; i < lbFeature.length; i++)
	    this.lbFeature[i] = Double.parseDouble(lbFeature[i]);
    }

    /**
     * Tree node
     * 
     * @author tigerzhong
     */
    private class Node implements java.io.Serializable {
	private static final long serialVersionUID = 1L;
	public boolean leafFlag = false;	//Leaf flag
	public double splitValue;		//Point value in the feature used for splitting
	public int splitIdx;			//The index of the feature used for splitting
	public double dataDistribution[];	//Classes information at one node
	public int numData;			//Number of instances at one node
    }

    /**
     * Trees, node set
     * 
     * @author tigerzhong
     * 
     */
    private class Tree implements java.io.Serializable {
	private static final long serialVersionUID = 1L;
	public Node nodes[];					//Node set
	public Tree() {
	    nodes = new Node[(int) Math.pow(2, depth + 1)];	//Completed binary tree
	    for (int i = 0; i < nodes.length; i++) {
		nodes[i] = new Node();
	    }
	}
    }

    /**
     * Build Classifier
     */
    public void buildClassifier() throws Exception {
	init();
	generateTrees();
    }

    /**
     * Initialize the random trees
     */
    public void init() {
	forest = new Tree[numTrees];
	ubFeature = new double[numFeatures];
	lbFeature = new double[numFeatures];
	for (int i = 0; i < numTrees; i++) {
	    forest[i] = new Tree();
	}
    }

    /**
     * Generate Trees
     */
    private void generateTrees() {
	for (int i = 0; i < numTrees; i++) {
	    buildTree(0, 0, i);
	}
    }

    /**
     * Build single tree
     * 
     * @param depth
     * @param nodeID
     * @param treeID
     */
    private void buildTree(int dp, int nid, int tid) {
	/*Too deep*/
	if (dp >= depth) {
	    forest[tid].nodes[nid].leafFlag = true;
	    forest[tid].nodes[nid].splitIdx = -1;
	    forest[tid].nodes[nid].splitValue = Double.MIN_VALUE;
	    forest[tid].nodes[nid].dataDistribution = new double[numClass];
	    forest[tid].nodes[nid].numData = 0;
	    return;
	}
	// Get the split feature randomly
	int splitIdx = MyMath.generateRand(0, numFeatures);
	// Get the split value randomly
	double splitValue = MyMath.generateRand(lbFeature[splitIdx],
		ubFeature[splitIdx]);
	forest[tid].nodes[nid].leafFlag = false;
	forest[tid].nodes[nid].splitIdx = splitIdx;
	forest[tid].nodes[nid].splitValue = splitValue;
	forest[tid].nodes[nid].dataDistribution = new double[numClass];
	forest[tid].nodes[nid].numData = 0;
	//Build the sub-trees
	buildTree(dp + 1, nid * 2 + 1, tid);
	buildTree(dp + 1, nid * 2 + 2, tid);
    }

    /**
     * Detect which nodes one instance reaches
     * 
     * @param rowData
     * @return The list containing the positions of one instance
     */
    public List<String> goThroughTree(String rowData[]) {
	List<Double> item = new ArrayList<Double>();
	for (int f = 0; f < numFeatures; f++) {
	    double defaultvalue = 0.0;
	    if (!rowData[f].equals(""))
		defaultvalue = Double.parseDouble(rowData[f]);
	    item.add(defaultvalue);
	}
	List<String> res = new ArrayList<String>();
	for (int i = 0; i < numTrees; i++) {
	    int nid = 0;
	    while (!forest[i].nodes[nid].leafFlag) {
		int si = forest[i].nodes[nid].splitIdx;		//Get index
		double sv = forest[i].nodes[nid].splitValue;	//Get split point value
		if (item.get(si) < sv) // Left
		    nid = nid * 2 + 1;
		else
		    nid = nid * 2 + 2; // Right
	    }
	    res.add(i + "," + nid);    // output: [tree id],[node id]
	}
	return res;
    }
    
    /**
     * Fill model with statistic information
     * @param localFileURl
     * @param HDFSFileURl
     * @param localModelName
     * @param HDFSFileName
     * @throws Exception
     */
    public static void fillModel(String localFileURl, String HDFSFileURl, String localModelName, String finalName, String HDFSFileName)
	    throws Exception {
	//Copy file from HDFS to local disk
	HadoopUtil.HDFSFile2Local(true, HDFSFileURl, localFileURl);
	//Local directory of statistic information
	File directory = new File(localFileURl+"out");
	File files[] = directory.listFiles();
	//Load model from hard disk. 
	RDTModel model = ModelOperator.loadModel(localModelName);
	for (File file : files) {
	    if (!file.isFile() || !file.getName().startsWith("part-"))	//Filter
		continue;
	    Scanner inFile = new Scanner(file);
	    while (inFile.hasNext()) {
		/*Key, Assume the format should be [tree id],[node id]*/
		String ids[] = inFile.next().split(",");
		if (ids.length != 2)
		    continue;
		/*Value, [Class information],[Number of instances]*/
		String items[] = inFile.next().split(",");
		double cnt[] = new double[items.length];
		for (int i = 0; i < items.length; i++){
		    cnt[i] = Double.parseDouble(items[i]);
		}
		/*Fill the empty tree with one record*/
		model.fillTree(Integer.parseInt(ids[0]), Integer
			.parseInt(ids[1]), cnt);		
	    }
	    inFile.close();
	}
	//Save model, Attention: localModelName != finalName !!!!!
	ModelOperator.saveModel(model, finalName, HDFSFileName);
    }

    /**
     * Fill model with one data point
     * 
     * @param tid
     * @param nid
     * @param cnt
     * @param value
     */
    public void fillTree(int tid, int nid, double cnt[]) {
	int nc = cnt.length;
	/*Filling and */
	while (nid > 0) {
	    for (int i = 0; i < nc-1; i++) {
		forest[tid].nodes[nid].dataDistribution[i] += cnt[i];
	    }
	    forest[tid].nodes[nid].numData += cnt[nc-1];
	    nid = (nid - 1) / 2;
	}
	for (int i = 0; i < nc-1; i++) {
	    forest[tid].nodes[0].dataDistribution[i] += cnt[i];
	}
	forest[tid].nodes[0].numData += cnt[nc-1];
    }

    /**
     * Classify one instance
     * 
     * @param rowData
     * @return Prediction values
     */
    public double[] classifyInstance(String rowData[]) {
	/*Transform*/
	List<Double> item = new ArrayList<Double>();
	double preValue[] = new double[numClass];
	for (int f = 0; f < rowData.length; f++) {
	    double defaultvalue = 0.0;
	    if (!rowData[f].equals(""))
		defaultvalue = Double.parseDouble(rowData[f]);
	    item.add(defaultvalue);
	}
	/*Go through each tree*/
	for (int i = 0; i < numTrees; i++) {
	    int nid = 0;
	    while (!forest[i].nodes[nid].leafFlag) {
		//Pure
		double largest = -1;
		for (int di = 0; di < numClass; di++) {
		    if (forest[i].nodes[nid].dataDistribution[di] > largest)
			largest = forest[i].nodes[nid].dataDistribution[di];
		}
		if (largest >= forest[i].nodes[nid].numData*ratio || forest[i].nodes[nid].numData<minNum)
		    break;
		//Go down
		int si = forest[i].nodes[nid].splitIdx;
		double sv = forest[i].nodes[nid].splitValue;
		if (item.get(si) < sv){	//Left
		    if(forest[i].nodes[nid * 2 + 1].numData>=minNum)
			nid = nid * 2 + 1;
		    else break;
		}
		else{	//Right
		    if(forest[i].nodes[nid * 2 + 2].numData>=minNum)
			nid = nid * 2 + 2;
		    else break;
		}
	    }
	    // Get the results 
	    double pre[] = new double[numClass];
	    for (int k = 0; k < numClass; k++) {
		pre[k] = forest[i].nodes[nid].dataDistribution[k]
			/ forest[i].nodes[nid].numData;
	    }
	    for (int j = 0; j < numClass; j++) {
		preValue[j] += pre[j];
	    }
	}
	//Average
	for (int j = 0; j < numClass; j++) {
	    preValue[j] = preValue[j] / numTrees;
	}
	return preValue;
    }

}
